package com.neusoft.circle.single;

import com.neusoft.entity.Boy;

import java.util.Objects;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 单向环形链表实现类
 * @date 2024-06-13
 */
public class SingleCircleLinkedList {

    /**
     * 头节点
     */
    private Node<Boy> firstNode = null;

    /**
     * 添加节点
     *
     * @param nodeNum 添加节点的数量
     */
    public void addNode(int nodeNum) {
        if (nodeNum < 1) {
            System.out.println("请输入正确的节点数");
            return;
        }

        // 辅助节点，帮助构建环形链表
        Node<Boy> currentNode = null;
        for (int i = 1; i <= nodeNum; i++) {
            Node<Boy> node = new Node<>(new Boy(i));
            // 判断是否为第一个节点
            if (i == 1) {
                firstNode = node;
                // 构成环形
                firstNode.setNextNode(firstNode);
                // 让currentNode指向第一个节点
                currentNode = firstNode;
            } else {
                currentNode.setNextNode(node);
                node.setNextNode(firstNode);
                currentNode = node;
            }
        }
    }

    /**
     * 遍历打印单向环形链表中的数据
     */
    public void list() {
        if (Objects.isNull(firstNode)) {
            System.out.println("没有任何节点~~");
            return;
        }

        // 辅助节点，帮助完成遍历
        Node<Boy> currentNode = firstNode;
        while (true) {
            System.out.printf("小孩的编号: %d \n", currentNode.getItem().getNo());
            // 说明已经遍历完毕
            if (currentNode.getNextNode() == firstNode) {
                break;
            }
            // currentNode后移
            currentNode = currentNode.getNextNode();
        }
    }

    /**
     * 根据起始编号和移动次数，计算出出圈顺序: 约瑟夫问题的代码实现
     *
     * @param startNo  从第几个节点开始数
     * @param countNum 一次性数几个节点
     * @param nodeNum  圈内初始有几个节点
     */
    public void calcPop(int startNo, int countNum, int nodeNum) {
        // 先对数据进行校验
        if (Objects.isNull(firstNode) || startNo < 1 || startNo > nodeNum) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }

        // 辅助指针, 帮助完成节点出圈
        Node<Boy> helpNode = firstNode;
        // helpNode事先应该指向环形链表的最后这个节点
        while (helpNode.getNextNode() != firstNode) {
            helpNode = helpNode.getNextNode();
        }

        // 出圈前，先让first和helper移动k-1次
        for (int j = 0; j < startNo - 1; j++) {
            firstNode = firstNode.getNextNode();
            helpNode = helpNode.getNextNode();
        }

        while (helpNode != firstNode) {
            // 让firstNode和helpNode指针同时移动countNum-1
            for (int j = 0; j < countNum - 1; j++) {
                firstNode = firstNode.getNextNode();
                helpNode = helpNode.getNextNode();
            }
            // 这时firstNode指向的节点，就是要出圈的节点
            System.out.printf("节点%d出圈\n", firstNode.getItem().getNo());
            // 这时将firstNode指向的节点出圈
            firstNode = firstNode.getNextNode();
            helpNode.setNextNode(firstNode);
        }
        System.out.printf("最后留在圈中的节点编号%d\n", firstNode.getItem().getNo());
    }
}
